GF(2)
GF(2) (also denoted , Z/2Z or ) is the finite field with two elements.[1][a]
GF(2) is the field with the smallest possible number of elements, and is unique if the additive identity and the multiplicative identity are denoted respectively 0 and 1, as usual.
The elements of GF(2) may be identified with the two possible values of a bit and to the Boolean values true and false. It follows that GF(2) is fundamental and ubiquitous in computer science and its logical foundations.
Definition
[edit]GF(2) is the unique field with two elements with its additive and multiplicative identities respectively denoted 0 and 1.
Its addition is defined as the usual addition of integers but modulo 2 and corresponds to the table below:
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
If the elements of GF(2) are seen as Boolean values, then the addition is the same as that of the logical XOR operation. Since each element equals its opposite, subtraction is thus the same operation as addition.
The multiplication of GF(2) is again the usual multiplication modulo 2 (see the table below), and on Boolean variables corresponds to the logical AND operation.
| × | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
GF(2) can be identified with the field of the integers modulo 2, that is, the quotient ring of the ring of integers Z by the ideal 2Z of all even numbers: GF(2) = Z/2Z.
Notations Z2 and may be encountered although they can be confused with the notation of 2-adic integers.
Properties
[edit]Because GF(2) is a field, many of the familiar properties of number systems such as the rational numbers and real numbers are retained:
- addition has an identity element (0) and an inverse for every element;
- multiplication has an identity element (1) and an inverse for every element but 0;
- addition and multiplication are commutative and associative;
- multiplication is distributive over addition.
Properties that are not familiar from the real numbers include:
- every element x of GF(2) satisfies x + x = 0 and therefore −x = x; this means that the characteristic of GF(2) is 2;
- every element x of GF(2) satisfies x2 = x (i.e. is idempotent with respect to multiplication); this is an instance of Fermat's little theorem. GF(2) is the only field with this property (Proof: if x2 = x, then either x = 0 or x ≠ 0. In the latter case, x must have a multiplicative inverse, in which case dividing both sides by x gives x = 1. All larger fields contain elements other than 0 and 1, and those elements cannot satisfy this property).
Applications
[edit]Because of the algebraic properties above, many familiar and powerful tools of mathematics work in GF(2) just as well as other fields. For example, matrix operations, including matrix inversion, can be applied to matrices with elements in GF(2) (see matrix ring).
Any group (V,+) with the property v + v = 0 for every v in V is necessarily abelian and can be turned into a vector space over GF(2) in a natural fashion, by defining 0v = 0 and 1v = v for all v in V. This vector space will have a basis, implying that the number of elements of V must be a power of 2 (or infinite).
In modern computers, data are represented with bit strings of a fixed length, called machine words. These are endowed with the structure of a vector space over GF(2). The addition of this vector space is the bitwise operation called XOR (exclusive or). The bitwise AND is another operation on this vector space, which makes it a Boolean algebra, a structure that underlies all computer science. These spaces can also be augmented with a multiplication operation that makes them into a field GF(2n), but the multiplication operation cannot be a bitwise operation. When n is itself a power of two, the multiplication operation can be nim-multiplication; alternatively, for any n, one can use multiplication of polynomials over GF(2) modulo a irreducible polynomial (as for instance for the field GF(28) in the description of the Advanced Encryption Standard cipher).
Vector spaces and polynomial rings over GF(2) are widely used in coding theory, and in particular in error correcting codes and modern cryptography. For example, many common error correcting codes (such as BCH codes) are linear codes over GF(2) (codes defined from vector spaces over GF(2)), or polynomial codes (codes defined as quotients of polynomial rings over GF(2)).
Algebraic closure
[edit]Like any field, GF(2) has an algebraic closure. This is a field F which contains GF(2) as a subfield, which is algebraic over GF(2) (i.e. every element of F is a root of a polynomial with coefficients in GF(2)), and which is algebraically closed (any non-constant polynomial with coefficients in F has a root in F). The field F is uniquely determined by these properties, up to a field automorphism (i.e. essentially up to the notation of its elements).
F is countable and contains a single copy of each of the finite fields GF(2n); the copy of GF(2n) is contained in the copy of GF(2m) if and only if n divides m. The field F is countable and is the union of all these finite fields.
Conway realized that F can be identified with the ordinal number , where the addition and multiplication operations are defined in a natural manner by transfinite induction (these operations are however different from the standard addition and multiplication of ordinal numbers).[2] The addition in this field is simple to perform and is akin to Nim-addition; Lenstra has shown that the multiplication can also be performed efficiently.[3]
See also
[edit]References
[edit]- ^ GF is the initialism of Galois field, another name for finite fields.
- ^ Lidl, Rudolf; Niederreiter, Harald (1997). Finite fields. Encyclopedia of Mathematics and Its Applications. Vol. 20 (2nd ed.). Cambridge University Press. ISBN 0-521-39231-4. Zbl 0866.11069.
- ^ Conway, John H. (2000). On Numbers and Games (2nd ed.). Wellesley, Mass. p. 61. ISBN 978-1-56881-127-7.
{{cite book}}: CS1 maint: location missing publisher (link) - ^ Lenstra, Hendrik (1977). "On the Algebraic Closure of Two" (PDF). Indagationes Mathematicae (Proceedings). 80 (5): 389–396. doi:10.1016/1385-7258(77)90053-1.